package week_six;

public class NumberOfLongestIncreasingSubsequence_673 {

    //状态 f[i]
    //状态转移 f[i] = max{ f[j] + 1} (j<i, nums[j]<nums[i])
    //边界 f[i]=1 (0<=i<n)
    public int findNumberOfLIS(int[] nums) {
        int length = nums.length;
        //数组f，记忆状态
        int[] f = new int[length];
        //数组count，记录每个f[i]的组合数量
        int[] count = new int[length];
        int max = 0;
        int ans = 0;
        for (int i = 0; i < length; i++) {
            f[i] = 1;
            count[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    // f[i]=Math.max(f[i], f[j]+1);
                    // System.out.println("i max: "+i+", f[j]: "+f[j]);
                    if (f[i] < (f[j] + 1)) {
                        f[i] = f[j] + 1;
                        count[i] = count[j];
                    } else if (f[i] == f[j] + 1) {
                        count[i] += count[j];
                    }
                }
            }
            max = Math.max(max, f[i]);
        }
        for (int x = 0; x < length; x++) {
            if (f[x] == max) {
                ans += count[x];
            }
        }
        return ans;

    }
}
